338. Counting Bits

tags: Easy、Bitwise

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

解法1: 餘數計算

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* countBits(int n, int* returnSize) {
    * returnSize = n + 1;
    int *array = malloc((n + 1) * sizeof(int));
    for (int i = 0; i < n+1; i++) {
        int temp = i;
        int count = 0;
        array[i] = 0;
            while (temp > 0) {
                if (temp % 2 == 1) {
                    count++;
                }
                temp = temp / 2;
        }
        array[i] = count;
    }
    return array;
}

解法2: 位元運算+動態規劃

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* countBits(int n, int* returnSize) {
    * returnSize = n + 1;
    int *array = (int*)malloc((n + 1) * sizeof(int));
    for (int i = 0; i < n+1; i++) {
        *(array + i) = 0;
        *(array + i) = *(array + (i >> 1)) + (i & 1);
    }
    return array;
}

191. Number of 1 Bits

tags: Easy、Bitwise

Write a function that takes the binary representation of a positive integer and returns the number of
set bits
it has (also known as the Hamming weight).

解法1:

int hammingWeight(int n) {
    int count = 0;
    while (n > 0) {
        int i = n % 2;
        count += i;
        n = n / 2;
    }
    return count;
}

解法2:

int hammingWeight(int n) {
    int count = 0;
    while (n > 0) {
        if (n & 1) {count++;}
        n >>= 1;
    }
    return count;
}